package com.yuxi.al.leercode;

/**
 * Created by yuxi on 2017/7/18.
 */
public class Jumper {
    public static void main(String[] args) {
        System.out.println(jumer(10));
    }

    /**
     * 假设一个青蛙一次可以跳一步 也可以跳两步  或者可以跳n步，求青蛙跳n步台阶有多少种跳法
     * 当n=1时 f(1) = 1;
     * 当n=2时 f(2) = f(2-1)+f(2-2);
     * 当n=3时 f(3) = f(3-1)+f(3-2)+f(3-3);
     * 当n=n-1时 f(n-1) = f(n-2)+f(n-3)+.....f(n-n);
     * 当n=n 时 f(n) = f(n-1)+f(n-2)+.....f(n-n);
     * so  f(n) = 2f(n-1);
     *
     * @param n
     * @return
     */
    private static int jumer(int n) {
        if (n <= 0) return 0;
        if (n == 1) {
            return 1;
        }
        return 2 * jumer(n - 1);
    }
}
